package leetcode.hot100;

@SuppressWarnings("all")
public class _79_单词搜索 {

    // 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false
    // 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格
    // 同一个单元格内的字母不允许被重复使用

    char[][] board;
    char[] chars;
    int len;
    boolean[][] visited;
    static final int[][] DIRECTIONS = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) return false;
        this.board = board;
        this.chars = word.toCharArray();
        this.len = word.length();
        this.visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 从(i,j)位置为起点，在二维数组中找到以word.chatAt(0)开头的字符后
                // 再以word.chatAt(0)为起点向上下左右四个方向查找是否存在完整的单词
                if (dfs(i, j, 0)) {
                    return true;
                }
                // dfs方法返回false就会去寻找下一个起点位置
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, int begin) {
        // 如果单词就一个字符，那么只要当前位置的字符和该字符相等即可
        if (begin == len - 1) {
            return board[x][y] == chars[begin];
        }
        // 从首字符搜寻其他剩余字符的起点
        if (board[x][y] == chars[begin]) {
            visited[x][y] = true;
            // 以当前字符为中心向上下左右四个方向搜索它的下一个字符是否存在
            for (int[] direction : DIRECTIONS) {
                int newX = x + direction[0];
                int newY = y + direction[1];
                if (inArea(newX, newY) && !visited[newX][newY]) {
                    if (dfs(newX, newY, begin + 1)) {
                        return true;
                    }
                }
            }
            // 撤销之前的标记
            visited[x][y] = false;
        }
        return false;
    }

    boolean inArea(int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }

    /**
     * 递归把握什么？
     * 关注当前考察的点，处理它，其他丢给递归子调用去做
     * 判断当前选择的点，本身是不是一个错的点
     * 剩下的字符能否找到路径，交给递归子调用去做
     * 如果当前点是错的，不用往下递归了，返回false，否则继续递归四个方向，为剩下的字符选点
     * 那么，哪些情况说明这是一个错的点：
     * 1、当前的点，越出矩阵边界
     * 2、当前的点，之前访问过，不满足「同一个单元格内的字母不允许被重复使用」
     * 3、当前的点，不是目标点，比如你想找 E，却来到了 D
     */
}
